#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int res=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){res=(res<<1)+(res<<3)+(c^48);c=getchar();}
	return res*f;
}
void write(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int n;
int vis[10000005],prim[10000005],cnt,val[10000005];
void init()
{
	for(int i=2;i<=1e7;i++)
	{
		if(!vis[i])
		{
			prim[++cnt]=i;
			val[i]=i;
		}
		for(int j=1;j<=cnt&&i*prim[j]<=1e7;j++)
		{
			vis[i*prim[j]]=1;
			val[i*prim[j]]=min(val[i*prim[j]],prim[j]);
			if(i%prim[j]==0) break;
		}
	}
}
signed main()
{
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout);
	memset(val,0x3f,sizeof val);
	init();
	n=read();
	while(n--)
	{
		int a=read(),b=read();
		if(__gcd(a,b)>1)
		{
			if(a%b==0) write(a);
			else if(b%a==0) write(b);
		 	else write(a+b); 
		}
		else 
		{
			int ans=a*b;
			ans=min(ans,min(a+val[a]*b,b+val[b]*a));
			ans=min(ans,a+b+val[a]*val[b]);
			ans=min(ans,min(2*a+2*val[b]/__gcd(2ll,val[b])+b,2*b+2*val[a]/__gcd(2ll,val[a])+a));
			ans=min(ans,2*a+2*b);
			ans=min(ans,a+b+val[a]*2+val[b]*2);
			write(ans);
		}
		puts("");
	}
	return 0;
}
/*
1
303 403

738
*/
